#include<iostream>
#include<set>
#include<map>
using namespace std;

//int main()
//{
//	/*map<string, int> m = { {"923",1},{"3423",2} };
//
//	set<int> s = { 1,2,1,4 };
//
//	map<string, int>::iterator it = m.begin();
//	while (it != m.end())
//	{
//		cout << it->first << ":" << it->second << endl;
//		it++;
//	}*/
//	//cout << m["123"];
//
//
//
//	return 0;
//}

class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
Node* copyRandomList(Node* head) {
    if (head == nullptr)
        return nullptr;
    Node* cur = head;
    Node* copy = new Node(cur->val);
    Node* copycur = copy;
    cur = cur->next;
    while (cur)
    {
        Node* newnode = new Node(cur->val);
        copycur->next = newnode;
        copycur = newnode;
        cur = cur->next;
    }
    map<Node*, Node*> mp;
    cur = head;
    copycur = copy;
    while (cur)
    {
        mp.insert({ cur, copycur });
        cur = cur->next;
        copycur = copycur->next;
    }
    cur = head;
    copycur = copy;
    while (cur)
    {
        copycur->random = mp[cur->random];
        cur = cur->next;
        copycur = copycur->next;
    }

    return copy;
}
#include<string>
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
    
};
string tree2str(TreeNode* root) {
    string str;
    if (root == nullptr)
        return str;

    str += to_string(root->val);

    if (root->left || root->right)
    {
        str += "(";
        str += tree2str(root->left);
        str += ")";
    }
    if (root->right)
    {
        str += "(";
        str += tree2str(root->right);
        str += ")";
    }
    return str;
}
int main()
{
    TreeNode* root1 = new TreeNode(1);
    TreeNode* root2 = new TreeNode(2);
    TreeNode* root3 = new TreeNode(3);
    TreeNode* root4 = new TreeNode(4);

    root1->left = root2;
    root1->right = root3;
    root2->left = root4;

    string s = tree2str(root1);

    return 0;
}